#include <vector>
#include <string>

using namespace std;

// 967. 连续差相同的数字
class Solution 
{
    string path;
    vector<int> ret;

private:
    void dfs(int n, int index, int k)
    {
        // 找到了一个符合要求的答案
        if(index == n)
        {
            ret.push_back(stoi(path));
            return;
        }

        for(int i = 0; i <= 9; ++i)
        {
            // i 与前一位的差值相差 k，则 index 位置可以放入 i，然后继续往下递归
            if((path[index - 1] - '0' - i == k) || (i + '0' - path[index - 1] == k))
            {
               
                path += '0' + i;
                dfs(n, index + 1, k);
                path.pop_back();
            }
        }
    }

public:
    vector<int> numsSameConsecDiff(int n, int k) 
    {
        for(int i = 1; i <= 9; ++i)
        {
            // 先确定第一位避免前导零
            path += '0' + i;
            dfs(n, 1, k);
            path.pop_back();
        }
        return ret;
    }
};

// 1535. 找出数组游戏的赢家 
class Solution 
{
public:
    int getWinner(vector<int>& arr, int k) 
    {
        int n = arr.size(), pos = 0, maxVal = 0;
        // 找出元素最大值及其位置
        for(int i = 0; i < n; ++i)
        {
            if(arr[i] > maxVal)
            {
                pos = i;
                maxVal = arr[i];
            }
        }

        // 前面的元素赢不了 k 轮
        if(pos <= k) return maxVal;
        // 最大值在最前面，直接返回最大值
        if(pos == 0) return maxVal;
        // cnt；赢的轮数，pos1：处于位置零的元素
        int cnt = 0, pos1 = 0, j = 1;
        while(pos1 < pos)
        {
            if(arr[pos1] > arr[j])
            {
                ++j;
                ++cnt;
            }
            else
            {
                pos1 = j;
                cnt = 1;
                ++j;
            }
            if(cnt == k) return arr[pos1];
        }
        return maxVal;
    }
};